package oop.ex3.search;

import java.util.Date;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * A time and depth limited DFS for searchboard with optimizations for best quality boards
 * 
 * @author Kobi Atiya & Tsachi Holzberg
 * 
 * @param <B> the search board node
 * @param <M> the search move
 */
public class MyDepthFirstSearch<B extends SearchBoardNode<M>, M extends SearchMove> implements
        DepthFirstSearch<B, M> {

    @SuppressWarnings("unchecked")
    @Override
    public B search(B startBoard, int maxDepth, long timeOut) {
        long endTime = new Date().getTime() + timeOut;
        B bestBoard = (B) startBoard.getCopy();

        /* iterator stack for legal moves, instead of using an iterator */
        Deque<MovesIterator<M>> iteratorStack = new LinkedList<MovesIterator<M>>();
        MovesIterator<M> iterator = new MovesIterator<M>(startBoard.getMovesIterator());

        while (new Date().getTime() <= endTime) {
            /* Depth limit or no more moves available */
            if (!iterator.hasNext() || maxDepth == 0) {
                if (iteratorStack.isEmpty()) {
                    break;
                }
                maxDepth++;
                iterator = iteratorStack.pop();
                startBoard.undoMove(iterator.getLastIterator());
                continue;
            }
            startBoard.doMove(iterator.next());
            /* Quality upper bound optimization */
            if (startBoard.getQualityBound() <= bestBoard.getQuality()) {
                startBoard.undoMove(iterator.getLastIterator());
                continue;
            }
            /* If it's the best board */
            if (startBoard.isBestSolution()) return startBoard;

            /* Swapping bestBoard candidate with a better candidate */
            if (startBoard.getQuality() > bestBoard.getQuality()) {
                bestBoard = (B) startBoard.getCopy();
            }
            maxDepth--;
            iteratorStack.push(iterator);
            iterator = new MovesIterator<M>(startBoard.getMovesIterator());
        }
        return bestBoard;

    }

    /**
     * A {@link Iterator} that supplies an access to the last moveIterator
     * 
     * @author Kobi Atiya
     * @author Tsachi Holzberg
     * 
     * @param <T> the Iterator Type
     */
    public static class MovesIterator<T> implements Iterator<T> {
        private Iterator<T> iterator;    // the iterator
        private T           lastIterator; // the last type

        /**
         * A Copy Constructor
         * 
         * @param iterator the iterator to copy from
         */
        public MovesIterator(Iterator<T> iterator) {
            this.iterator = iterator;
            lastIterator = null;
        }

        @Override
        public boolean hasNext() {
            return iterator.hasNext();
        }

        @Override
        public T next() {
            return lastIterator = iterator.next();
        }

        @Override
        public void remove() {
            iterator.remove();

        }

        public String toString() {
            MovesIterator<T> temp = new MovesIterator<T>(this);
            String output = "";
            while (temp.hasNext()) {
                output += temp.next().toString() + "\n";
            }
            return output;
        }

        /**
         * Returns the last object in the iterator, calling it before calling next() will return null
         * 
         * @return the last object in the iterator
         */
        public T getLastIterator() {
            return lastIterator;
        }

    }

}
